%\documentclass[11pt]{amsart} 
\documentclass[11pt]{article} 
\usepackage{amsmath,amsfonts,amssymb} 
\usepackage{array,delarray,xspace} 
\usepackage[dvips]{graphicx}
\usepackage{times} 
\usepackage{dsfont} 
%\usepackage[square,sort]{natbib} 
%\usepackage{citesort} 
\usepackage{xspace} 
\usepackage{psfrag}
\usepackage{subfigure}
\usepackage{epsfig}
\usepackage{graphics}
\usepackage{epic}
\usepackage{eepic}
\usepackage{color}
\usepackage{wrapfig}
\usepackage{multirow}
\usepackage{url}
\usepackage{smallhead}
\usepackage{fullpage}
 
%\usepackage[dark,bottomafter]{draftcopy}\draftcopySetGrey{0.995} 
%\usepackage[light,bottom,all]{draftcopy}\draftcopySetGrey{0.95} 
%\usepackage[light]{draftcopy}\draftcopyName{Abdul}{250}\draftcopySetGrey{0.95} 
\newcommand{\reviewtimetoday}[2]{\special{!userdict begin 
    /bop-hook{gsave 20 710 translate 45 rotate 0.90 setgray 
   /Times-Roman findfont 13 scalefont setfont 0 0   moveto (#1) show 
   0 -12 moveto (#2) show grestore}def end}} 
% You can turn on or off this option. 
%\reviewtimetoday{\today}{Draft Version} 
 

\newcommand{\ol}{\lambda^*}
\newcommand{\opi}{\overline{\pi}}
\newcommand{\bpi}{\boldsymbol{\pi}}
\newcommand{\bopi}{\overline{\boldsymbol{\pi}}}
\newcommand{\br}[1]{\boldsymbol{\mathrm{#1}}}
\newcommand{\bn}{\boldsymbol{n}}
\renewcommand{\b}[1]{\boldsymbol{#1}}
\newcommand{\wane}{a}
\newcommand{\Svalue}{\Phi}
\newcommand{\dt}[1]{\frac{\mathrm{d}{#1}}{\mathrm{d}t}}
\DeclareMathOperator*{\argmax}{\operatorname{argmax}}
\newcommand{\total}[2]{\frac{\mathrm{d}#1}{\mathrm{d}#2}}
\newcommand{\tot}[1]{\mathrm{d}#1}
\newcommand{\rd}[0]{\mathrm{d}}
\renewcommand{\path}[1]{\mathcal{D}#1}


\newcommand{\al}{\ensuremath{\alpha}} 
\newcommand{\be}{\ensuremath{\beta}} 
\newcommand{\ga}{\ensuremath{\gamma}} 
\newcommand{\eps}{\ensuremath{\epsilon}} 
 
\newcommand{\lcm}{\mathrm{lcm}} 
\newcommand{\dis}{\mathrm{dis}} 
 
\newcommand{\nn}{\mathds{N}} 
\newcommand{\zz}{\mathds{Z}} 
\newcommand{\rr}{\mathds{R}} 
\newcommand{\ff}{\mathds{F}} 
\newcommand{\pp}{\mathfrak{p}} 
\newcommand{\qq}{\mathfrak{q}} 
\newcommand{\kk}{\mathds{K}} 
\newcommand{\CG}{G}
\newcommand{\CN}{{\cal N}}
\newcommand{\attack}{$G_{\vec{a}}$}
\newcommand{\attackzero}{$G_{\vec{a}[v/0]}$}
\newcommand{\GNS}[1]{\mbox{{\sc GNS}}(#1)}
\newcommand{\cost}{\mbox{cost}}

\newcommand{\junk}[1]{} 
\newcommand{\BfPara}[1]{\noindent {\bf #1.}}
\newtheorem{theorem}{Theorem}[section]   % Numbered within each section 
 
\newtheorem{corollary}[theorem]{Corollary}  % Numbered along with thm 
 
\newtheorem{lemma}[theorem]{Lemma}         % Numbered along with thm 
 
\newtheorem{proposition}[theorem]{Proposition}  % Numbered along with thm 
 
%\theoremstyle{definition} 
\newtheorem{definition}[theorem]{Definition}   % Numbered along with thm 
 
%\theoremstyle{remark} 
\newtheorem{remark}[theorem]{Remark}        % Numbered along with thm 
 
\newtheorem{example}[theorem]{Example}        % Numbered along with thm 
 
\numberwithin{equation}{section}     % Number equations within sections 
 
\newcounter{listCounter}
\newcommand{\ListLengths}{\setlength{\itemsep}{0ex}\setlength{\topsep}{1ex}\setlength{\partopsep}{0ex}}

%% No indentation for the bullet.  The text is indented.  Little spacing.
\newenvironment{mylowitemize}{\begin{list}{$\bullet$}{\setlength{\leftmargin}{1em}\ListLengths}}{\end{list}}
 
%% No indentation for enumeration
\newenvironment{NoIndentEnumerate}{\begin{list}{\arabic{listCounter}.}{
        \usecounter{listCounter}\setlength{\leftmargin}{1em}\ListLengths}}{\end{list}}

\setlength{\textheight}{9in}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{0.0in}
%\setlength{\topmargin}{-0.30in}
%\setlength{\captionindent}{1.0pc}

\begin{document} 
\thispagestyle{empty} 
\junk{
\title{Project Description\\
Collaborative Research: The Role of Space and Time in Contagion}
%\title{Information and Interaction in Disease Transmission}
\maketitle 
}
\begin{center}
{\LARGE \bf
Project Description}

\bigskip

{\Large \bf Collaborative Research: The Role of Space and Time in Contagion}

\bigskip
\end{center}

\input{intro}
\input{related}

\section{Framework and Definitions}
\label{sec:prelim}

We briefly present our framework which incorporates locality of
information, behavioral changes that alter connections, and temporal
intervention strategies.  In the following, we use the SIR model for
epidemics as an illustrative example, but our framework, and the
associated questions are relevant for a broader class of contagion
processes.
\smallskip

Let $V$ denote the set of individuals/users/devices (henceforth,
referred to as \emph{nodes}), each of which is assumed to be an
autonomous player.  Let $G=(V,E)$ denote the underlying contact graph
over the node set $V$; an edge $e=(u,v)\in E$ indicates that nodes $u$
and $v$ are connected, and the diffusion can spread from $u$ to $v$.
We let $p(e,t)$ or $p(u,v,t)$ denote the probability that the
diffusion spreads from node $u$ to node $v$ at time step $t$; in the
cases where the probabilities are assumed to not vary with time, we
denote these by $p(e)$ or $p(u,v)$.  In animal disease models (e.g.,
foot and mouth), the nodes denote farms, and $p(u,v)$ varies as a
power of the distance between the farms $u$ and $v$. For $S\subset V$,
we let $G[S]$ denote the subgraph of $G[V]$ induced by the set $S$.
We assume that the infection is initiated at a node chosen from $V$
according to an arbitrary probability distribution; let $w_v$ denote
the probability that node $v$ is chosen as the initial infection
point, and let $w(S)=\sum_{v\in S} w_v$ for $S\subset V$. As mentioned
earlier, in most of the proposal, we consider the discrete time
\underline{S}usceptible-\underline{I}nfected-\underline{R}ecovered
(SIR) model of disease transmission, in which each infected node $u$
infects each susceptible neighbor $v$ independently with probability
$p(u,v,t)$ at time $t$ (see~\cite{durrett06,newman:spread02,Ne03} for
additional information).  Nodes which are successfully vaccinated are
assumed not to spread the infection.  An important aspect of our
framework is that vaccines (and other interventions) are only
partially efficacious, and a vaccine succeeds only with probability
$p_s$.  However, nodes do not know whether the vaccine has succeeded,
and might alter their behavior.  

The strategy for each node $v$ consists of two decisions:
\begin{enumerate}
\item
Whether and when to adopt an intervention, such as vaccination
(modeled by node deletion) or quarantining (modeled by deletion of
some edges); in most of this project description, we focus on
vaccination strategies. Let $a_{v,t}\in[0,1]$ denote the probability
that node $v$ gets vaccinated at time $t$; in the case where the
decisions are made at $t=0$, we sometimes drop the time subscript, and
denote this simply as $a_v$. Let $\vec{a}$ denote the strategy vector
of all nodes. We need the notion of \emph{attack graph}, denoted by
$G_{\vec{a}}$, which is the subgraph of $G$ in which each node is
deleted with probability $a_v$ \cite{AspnesCY2006}.
\item
Behavioral changes that alter connections: Such behavioral changes
could happen in many ways, and we abstract it by considering
$p_b(u,v,t)$, which denotes the modified transmission probability on
edge $(u,v)$ at time $t$. While the behavioral change could be
manifested as fairly general vectors $\vec{p_b}$, we focus on an
important special case where these changes occur only following an
intervention.  We consider two specific models -- in the {\em 1-sided
  model}, vertex $u$ after vaccination increases the transmission
probability to $p_b$ on all incident edges $(u,v)$, while in the {\em
  2-sided model}, vertex $u$ increases the transmission probability
only on edges $(u,v)$ for which vertex $v$ is also vaccinated.  
\end{enumerate}

The rationale behind the behavioral change models is that after
vaccination, it makes sense for an individual to take advantage of the
social contact network to enhance their economic value.  We formalize
this aspect below.  The 1- and 2-sided models signify two potential
ways in which the contagion spread could be affected: whether it
requires increased contact from any one endpoint, or both endpoints.
There are a number of natural hybrid models that we will also consider
in our study.  Since increased contact comes with increased risks, we
sometimes refer to this behavior change as ``risky behavior''.

The information used by nodes is an important aspect of the decision
making process, and we quantify this in terms of a parameter $d$,
which denotes the maximum number of hops to which a node can get
information about infections and/or vaccinations.  This kind of
information could be perfect (e.g., who all got vaccinated within the
$d$-neighborhood), or summary (e.g., how many people got vaccinated
within the $d$-neighborhood), or Bayesian (based on a probability
distribution on the structure and strategies in the
$d$-neighborhood~\cite{galeotti+gjvy:network}).

We now consider a generalized non-cooperative game formulation
$\mathcal{G}(G,d)$ by defining individual costs, which involve the
following components: (i) $C(v,t)$ denotes the cost of node $v$
getting vaccinated at time $t$; we assume this is independent of the
disease dynamics; (ii) $B(v)$ denotes the ``benefit'' of increased
contact (e.g., in the form of information and centrality of the node
in the social organization); and (iii) $L_v$ denotes the cost for node
$v$ resulting from an infection. We assume that node $v$ only has
information about the graph within its $d$-neighborhood; let
$p_v(\vec{a},\vec{p_b},d)$ denote the probability that node $v$
becomes infected, given the decision vectors $\vec{a}$ and
$\vec{p_b}$. Then, the cost to node $v$ is defined as
\[\cost_v\left(\bar{a},\vec{p_b},d\right) = C_v\sum_t a(v,t) + B_v\sum_t p_b(v,t)
+(1-\sum_t a(v,t))L_v\cdot p_v\left(\bar{a},\vec{p_b},d\right).\label{eqn:cost}\]

A Nash equilibrium (henceforth, NE) is a strategy vector $\vec{a}$
such that no node $v$ has any incentive to switch his strategy, if all
other nodes' strategies are fixed; in most of the proposal, we focus
on pure NE.  We consider variants in which the term
$p_v(\vec{a},\vec{p_b},d)$ using only partial information about the
graph and individual decisions within the $d$-neighborhood; as we
discuss later, information has a significant impact on the dynamics
and structure of NE in these games.
Another related notion is that of Stackelberg strategies \cite{roughgarden:sicomp04},
where we assume an administrator can control the strategy vectors
$(\vec{a_S}, \vec{p_{bS}})$ of a subset $S\subset V$ of the nodes, while the
remaining nodes in $V-S$ choose strategy vectors $(\vec{a_{V-S}}, \vec{p_{b,V-S}})$.
These pairs $(\vec{a_S}, \vec{p_{bS}})$ and $(\vec{a_{V-S}}, \vec{p_{b,V-S}})$
together form a Stackelberg strategy vector. This allows the administrator to control
the kinds of equilibria that are achieved.

The total social cost of a strategy profile is
the sum of the individual costs, which is $\cost\left(\bar{a}, \vec{p_b},d\right) =
\sum_{v=1}^n \cost_v\left(\bar{a}, \vec{p_b},d\right)$.  A socially optimum strategy
is a pair of vectors $\vec{a}, \vec{p_b}$ that minimizes this cost - this is not
necessarily (and is not usually) a pure NE. Therefore, the cost of a
pure NE relative to the social cost is an important measure; the
maximum such ratio (i.e., over all possible pure NE) is also known as
the \emph{price of anarchy}~\cite{koutsoupias99worst}.


\iffalse
\section{Model}
\label{sec:model}

In this paper, $G=(V,E)$ will denote an undirected contact graph with $V$
denoting a set of people (referred to as nodes) and 
$e=(u,v)\in E$ denoting a contact between nodes $u$ and $v$. We use a
discrete time
\underline{S}usceptible-\underline{I}nfected-\underline{R}ecovered (SIR) model
of disease transmission \cite{newman:sirev}, in which each susceptible node $u$
infects each neighbor $v$ independently with probability $p_t$. An infected
node is assumed to recover in one time step. Each vertex $u$ in the graph is
either vaccinated or not (\uv). The vaccine succeeds with probability
$\ps$ (a vertex $u$ is labeled as \vs if its vaccination succeeds); 
if it fails, a vaccinated node $u$ (labeled as \vf) could become infected and
participate in the disease transmission. We assume that vaccinated nodes
do not know if the vaccine succeeded or not, and they increase
contacts to some of their neighbors, resulting in increased transmission
probability $\pb$ - in the Type 1 process, vertex $u$ increases the transmission
probability to $\pb$ on all incident edges $(u,v)$, while in the Type 2 
process, vertex $u$ increases the transmission probability only on edges
$(u,v)$ for which vertex $v$ is also vaccinated. In most of the paper, we
assume vertices are vaccinated randomly, with some probability, denoted by $\pv$.

Therefore, the above percolation process is defined by the tuple 
$(\pt,\pv,\ps,\pb)$ in the following manner: every vertex is labeled
\uv, \vs, \vf\ with probability $1-\pv$, $\pv\ps$ and $\pv(1-\ps)$,
respectively. All vertices labeled \vs are removed from the network.
Each edge $(u,v)$ connecting two surviving vertices $u$ and $v$,
is ``open'' (or retained in the graph, in the language of percolation, which
corresponds to disease transmission on this edge), or ``closed'' (or removed from
the graph), with some probability depending on the model - 
(i) in the Type 1 process, edge $e=(u,v)$ is open with probability $\pt$, if both
$u$ and $v$ are unvaccinated (i.e., labeled \uv), and is open with probability
$\pb$ if one of $u$ and $v$ is labeled \vf; (ii) in the Type 2 process,
edge $e=(u,v)$ is open with probability $\pt$, unless \emph{both} $u$ and $v$
are labeled \vf. Following the well known correspondence between bond
percolation and disease transmission, the connected component containing
a specific node $u$ is the (random) subset of nodes infected, if the disease
starts at $u$. If the components resulting from one random instance of the
above stochastic process are $C_1,\ldots,C_k$, then 
$\sum_i |C_i|^2/n$ denotes the average outbreak size if the disease starts
at a random initial node (this quantity is also called the \emph{susceptibility}
by Janson \cite{janson}). In our analysis, we consider the largest connected
component, or the susceptibility measure.

\fi


\section{Specific Research Tasks}
\input{sec4glue}
\subsection{Spatial constraints and strategies}
\label{sec:task1}
We begin with a focus on the spatial aspect of our framework: when
constraints and strategies are based only on the network structure,
and are not time-varying.  We consider the impact of (i) locality of
information (about others' states and strategies), quantified by the
parameter $d$ (as discussed in Section \ref{sec:prelim}); and (ii)
strategies that alter connections, as encapsulated by the vector
$\vec{p_b}$ which determines the changes in contagion transmission
probabilities on incident edges.  Note that here we assume there is no
temporal dimension to the strategy space in this case.  As we discuss
below, this is already a rich problem space -- is a product of the
many choices (or models) along each of these two dimensions; below, we
highlight some of the interesting tasks.

\iffalse
In this task, we consider on the case where $d=\infty$, so that all nodes have the same
information. 
We assume the decision about behavioral changes are encapsulated as
the single parameter $p_b$.
\fi

\smallskip
\noindent
\BfPara{Task 1: Games with static connections} We first consider the
case where there are no connection-altering interactions.  Here, the
strategy space for each node is binary: whether to vaccinate.  Since
there is no temporal dimension, the vaccination decision of node $v$
can be denoted by $a_v$ (as discussed in Section
\ref{sec:prelim}). Therefore, the cost function for $v$ is
$\cost_v\left(\bar{a}\right) = C_va_v + (1- a_v)L_v\cdot
P_v\left(\bar{a}\right)$; recall that $P_v(\bar{a})$ denotes the
probability that node $v$ gets infected, if the disease starts at a
random initial node in the $d$-neighborhood of $v$, i.e., $\{w\in V:
d_G(v,w)\leq d\}$.  As discussed in Section \ref{sec:prelim}, there is
an underlying diffusion process, and $p(e)$ denotes the probability
that the disease spreads on edge $e$.  \iffalse -- this corresponds to
the probability that node $v$ gets infected if the disease starts at a
random node in the attack graph $G_{\vec{a}}$ (the addition of
percolation to the problem is the main, and significant, difference
from the model of \cite{AspnesCY2006}). Note that this class of models
requires complete information about the graph and strategies.  \fi The
specific questions we study in this case include:
\begin{enumerate}
\item
Under what conditions do NE exist, when information (about the
individual strategies and disease states) is available only within the
$d$-neighborhood?  If NE exist, when are they unique and how robust
are they to perturbations in the network or locality of information?
What is the computational complexity of finding NE or reaching NE via
best-response dynamics?  What is the effect of the underlying network
(e.g., the degree sequence and conductance)?  Can we characterize the
kinds of nodes that tend to get vaccinated in any NE?  \junk{ Since
  pure NE do not always exist in general for $1<d<\infty$, are there
  ``approximate'' equilibria (in which no node gets too much
  additional payoff by switching). Also}

\item
Social optimum and price of anarchy: Find a vaccination strategy
$\vec{a}$ that minimizes the total cost.  What is the maximum ratio of
the cost of a social optimum and cost of NE (referred to as the price
of anarchy)?  What are practical strategies that cause convergence to
a socially desirable NE?  
\end{enumerate}

\noindent
\emph{Technical approach and preliminary work.} We propose to attack
these problems using tools from algorithmic game theory,
complexity theory, and approximation algorithms.  In preliminary
work~\cite{kumar+rss:icdcs}, we have considered the special case where
the contagion is maximally infectious ($p(e) = 1$ for each edge $e$)
and interventions are perfect.  We find that the parameter $d$ has a
significant role in the structure of the resulting games.  Both the
extremes of $d=1$ and $d=\infty$ turn out to be ordinal potential
games, and a pure NE can be computed by best response dynamics -- that
is, every sequence of best response steps by the individual players
converges to a pure NE. However, for every $d\in (1, \infty)$, there
always exist instances which have no pure NE; further, deciding if a
pure NE exists is NP-complete, in general.  We also develop a linear
programming-based algorithm with an approximation guarantee of
$O(\log{n})$ for computing the social optimum, generalizing and
improving a result due to~\cite{AspnesCY2006}.  (A
logarithmic-approximation for the $d=\infty$ case was also obtained
independently by~\cite{chen+dk:vaccinate}.)  Finally, we also bound
the price of anarchy, when NE do exist, in terms of the expansion of
the network.

The general model with arbitrary disease transmission probabilities is
much more challenging to handle.  One of the first hurdles we face in
terms of best response functions or social cost optimization is that
with probabilistic transmissions, even the calculation of the cost for
an individual node can be shown to be \#P-hard~\cite{valiant79}.
Efficient approximations (using Monte Carlo simulations) can be
computed, however, leading to the questions: do ``approximate'' NE
exist and can they be efficiently found?  can social optimum be
well-approximated.  Again, we believe locality of information will
play a crucial role, though the exact nature seems unclear.  For
approximating the social optimum, we plan to pursue two directions.
One is by using the notion of cut-based decompositions of networks,
thanks to an elegant result of R\"acke that approximates arbitrary
networks by trees~\cite{racke:decompose} (note that vaccination and
quarantining strategies are equivalent to vertex and edge cuts,
respectively, in graphs).  The other is by building on work
of~\cite{chung+hl:giant09} for percolation in arbitrary finite graphs.
Their results imply that for constant-degree networks, the cost of an
intervention strategy is asymptotically dominated by those clusters
(obtained after applying the intervention) that have high second order
average degree, defined as $\sum_v d(v)^2/(\sum_v d(v))$, where $d(v)$
denotes the degree of node $v$ in the cluster.  It is still
challenging to extend these ideas to derive efficient approximation
algorithms.

We are particularly interested in knowing the structure of NE and its
implications on public policy.  In \cite{galvani+rc:influenza07}, we
have studied this particular issue for influenza.  The elderly have
the greatest risk of influenza mortality, yet children are responsible
for most of the transmission.  The long-standing recommendations of
CDC follow the dictates of individual self-interest and prioritize the
elderly for vaccination. However, preferentially vaccinating children
may dramatically reduce community-wide influenza transmission.  A
potential obstacle to this is that the personal utility of vaccination
is lower for children than it is for the elderly. We parameterize an
epidemiological game theoretic model of influenza vaccination with
questionnaire data on actual perceptions of influenza and its vaccine
to compare NE strategies driven by self-interest with utilitarian
strategies for both epidemic and pandemic influenza. As shown in
Figure~\ref{fig:reluga_flu}, we observe that there is a significant
difference between the Nash and utilitarian vaccination levels.

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=3in]{tr-pnas.jpg}
\caption{
Variation in the probability of vaccination with cost; the $y$-axis denotes the probability of vaccination and the $x$-axis the cost \cite{galvani+rc:influenza07}.
}
\label{fig:reluga_flu}
\end{center}
\end{figure}

We believe that the structure of NE may affect public policy even if
all utilities are identical.  In simulations using the preferential
attachment model~\cite{kumar+rss:icdcs}, we have observed that high
degree nodes tend to get vaccinated in NE (when they exist).  This
suggests that from a public policy standpoint, it may be more prudent
to {\em not}\/ target high degree nodes if their cost structure
suggests they would protect themselves.  We plan to rigorously analyze
such {\em Stackelberg}\/ strategies, in which the choices of some
nodes could be controlled by the policy planner, and the goal would be
to design low cost strategies that cause the remaining nodes to reach
a ``good'' NE.  Of course, such policies also run the risk of {\em
  moral hazard}, whereby nodes may indulge in risky behavior,
enhancing their network connections following an intervention; this
leads us to the next major task of this project.

\smallskip
\BfPara{Task 2: Games with connection-altering interactions} We now
consider models with behavioral changes; as before, the locality is
parametrized by the parameter $d$, and, additionally, these decisions
are made at time $t=0$.  Among possible models for behavioral changes,
we focus on the 1-sided and 2-sided model (defined in Section
\ref{sec:prelim}).  \junk{ As discussed below, we find that this model
  exhibits counter-intuitive effects, such as non-monotonicity of the
  cost, as a function of $a_{vacc}$.  } The specific questions we
study include:
\begin{enumerate}
\item
How do the properties of NE (from Task 1) get affected by the
behavioral change parameter $p_b$ and the vaccine efficacy?  Are there
threshold phenomena involving these parameters, so that increase in
$p_b$ beyond a threshold value $p_b^{th}$ changes the dynamics
significantly? How does the difference between the cost of NE and
social optima (the price of anarchy) change (i.e., compared to Task
1)?  Further, for the more general case, what kinds of nodes choose to
get vaccinated and indulge in risky behavior in NE?

\item
Computing and characterizing the social optimum, i.e., the vaccination
strategy $\vec{a}$ that minimizes the total cost (when $p_b>0$) is a
challenging stochastic optimization question.  Can we achieve
equilibria that are close to social optimum through a public policy
that prioritizes vaccinations (subject to a budget) and provides
appropriate local and global information to individual players?
\end{enumerate}

\noindent
\emph{Technical approach and preliminary work.} As a first step
towards answering the above questions, we will focus on symmetric
strategies (in which the vaccination strategy $a_{vacc}$ and $p_b$ is
the same for all nodes), and understand how the disease dynamics
(e.g., the average outbreak size, and the time to peak) and the total
utility, $C_v a_{vacc} + B_v p_b +(1-\sum_t a_{vacc})L_v\cdot
P_v(a_{vacc}, p_b)$, vary as a function of $a_{vacc}$ and $p_b$.
Furthermore, answering the public policy issues would require
understanding the interplay between the locality parameter $d$ and the
behavioral change parameter $p_b$, which may depend significantly on
the vaccine efficacy and could be very different in the 1-sided and
2-sided models.

In preliminary work, we have studied special cases of Task 2,
especially the cost and structure of the social optimum, and the
differences between the 1-sided and 2-sided models. We assume that the
vaccines fail with probability $p_f$.  We find that both forms of risk
behavior change can lead to perverse outcomes across a wide range of
contact networks; 1-sided risk behavior change leads to perverse
outcomes at low levels of vaccination (in which the average outbreak
increases with $a_{vacc}$, up to a point, as shown in Figure
\ref{fig:mh}), while 2-sided risk behavior change leads to perverse
outcomes at high levels of vaccination (in which the average outbreak
size starts increasing beyond a threshold value of $a_{vacc}$). 

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=3in]{pa_1end_06_02_09.jpg}
\includegraphics[width=3in]{pa_2end_08_01.jpg}
\caption{ Variation in the giant component size with $a_{vacc}$ for
  the 1-sided and 2-sided models of risky behavior in scale-free
  graphs.  On the left is the comparison of uniform vaccination with
  two kinds of degree-preferred vaccination policies in the 1-sided
  model, for $p = 0.2$, $p_b = 0.9$, $p_f = 0.4$.  On the right are
  the curves for different values of behavior change probability $p_b$
  in the 2-sided model, for $p = 0.1$, $p_f = 0.2$.  The giant
  component size is a good estimate for the expected epidemic size.}
\label{fig:mh}
\end{center}
\end{figure}
We anticipate that a significant fraction of our efforts on Task 2
will be devoted to developing analytical tools.  Our initial foray has
been on Erd\"os-Renyi networks that have formed the basic underlying
network in traditional SIR models.  A major technical hurdle we face
is that when the behavioral models are incorporated, even homogeneous
Erd\"os-Renyi networks are transformed to heterogeneous networks.  One
powerful tool for analyzing percolation on heterogeneous networks is
that of {\em multi-type branching processes}.  We plan to build on
recent results of S\"oderberg~\cite{soderberg+inhomo02} and Bollobas
et al~\cite{bollobas+inhomo} in this regard.

Consider a random graph model denoted by
$\mathcal{G}(N,K,\textbf{r},\textbf{c})$, where (i) $K$ is a positive
integer, (ii) $\textbf{r}=\{r_1,\ldots,r_K\}$ is a probability vector,
(iii) $\textbf{c}=(c_{ij})$ is a $K\times K$ matrix, (iv) each node
$j=1,\ldots,N$, is assigned a type $i\in\{1,\ldots,K\}$ with
probability $r_i$, and (v) each pair of nodes $j, j'$ are connected by
an edge with probability
$p(j,j')=c_{ij}/N$. S\"{o}derberg~\cite{soderberg+inhomo02} and
Bollobas et al.~\cite{bollobas+inhomo} establish the following: (i) if
the eigenvalues of the matrix $\{c_{ij}r_j\}$ are all less than 1, it
is sub-critical (i.e., has no giant component), and (ii) if some
eigenvalue is larger than 1, it is super-critical (i.e., has a giant
component) with asymptotically $r_i(1-f_i)N$ nodes of type $i$, where
$f_i$ satisfies the coupled set of equations: $f_i = exp\left(\sum_j
c_{ij}r_j(f_j-1)\right)$.

Using the above thresholding result, we have given rigorous proofs for
the diverse non-monotonicity phenomena of Figure~\ref{fig:mh} in the case of
Erd\"os-Renyi random graphs.  Extending the analysis to more general
networks requires solving the above coupled equations and bounding the
fixed points $f_i$ in a more general setting, and appears to be
significantly more challenging.  We hope that generating function
techniques (e.g., MacMahon Master
Theorem~\cite[Chapter~1]{goulden+j:book}) would help us compute useful
bounds for relevant network families.  

Empirically, we have observed that the phenomenon is widespread across
a range of networks including preferential attachment networks.  We
are also applying traditional percolation theory techniques to the
class of locally-finite infinite
networks~\cite{bollobas:percolationBook} as a proof of concept.  Our
findings have implications for public policy and the distribution of
vaccines.  More surprisingly we observe that targeted vaccination can
be strictly worse than random vaccination for the same level of
vaccine coverage and this phenomenon occurs both for one-sided as well
as two-sided risk behavior change (as shown in Figure \ref{fig:mh}).
Given the prior work on targeting vaccine distributions this finding
flies in the face of intuition that expects that vaccinating highly
connected individuals would always confer greater benefits.

\junk{methods to mitigate the non-monotone
effects of behavioral changes, e.g., 

As
discussed below, the disease dynamics varies non-monotonically with
$p_b$, and characterizing the maximum/minimum is likely to be
important in this context.

}

\junk{



\subsubsection{Preliminary Work}
We have studied various aspects directly related to and forming a basis for the above
tasks, on a variety of models, ranging from compartmental to random graphs;
we summarize some of the most relevant ones here.
In \cite{kumar+rss:icdcs},
we study simplifications of Task 1.1, in which the disease transmission probability
is $p(e)=1$ for each edge. We develop an algorithm with an approximation guarantee
of $O(\log{n})$ for computing the social optimum (improving on the bound of
\cite{AspnesCY2006}). We also bound the price of anarchy in terms of the expansion
of the graph. We also find that in the preferential attachment model, high degree
nodes tend to get vaccinated in NE, which suggests that a good centralized strategy
need not target high degree nodes.
We find that the parameter $d$ has a significant
role in the structure of the
resulting games.  Both the extremes of $d=1$ and $d=\infty$
turn out to be ordinal potential games, and a pure NE can be computed
by best response dynamics -- that is, every sequence of best response
steps by the individual players converges to a pure NE. However, for
every $d\in (1, \infty)$, there always exist instances which have no pure NE;
further, deciding if a pure NE exists is NP-complete, in general. 

 We have also studied special cases of Task 1.2, especially the cost and structure of
the social optimum, and the differences between the 1-sided and 2-sided models. We
assume that the vaccines fail with probability $p_f$.
\iffalse
Let $S$ be the set of nodes that get vaccinated
initially (i.e., $S=\{v: a_v=1\}$), and let $S'\subset S$ be the set of nodes whose
vaccines fail. Then, in the Type-1 model, all nodes in $S$ increase the transmission
probability on all incident edges to $p_b$, while in the Type-2 model, the transmission
probability is increased only on edges $e=(u,v)$ with $u,v\in S'$. 
\fi
We find that both forms of risk behavior change can lead to perverse 
outcomes across a wide range of contact networks; 1-sided risk behavior change leads
to perverse outcomes at low levels of vaccination (in which the average outbreak 
increases with $a_{vacc}$, up to a point, as shown in Figure \ref{fig:mh}), 
while 2-sided risk behavior change leads to 
perverse outcomes at high levels of vaccination (in which the average outbreak size
starts increasing beyond a threshold value of $a_{vacc}$). We prove these phenomenon 
in heterogeneous Erdos-Renyi graphs 
using the tool of generating functions and in locally finite infinite networks using the techniques of 
percolation theory (discussed later in Section \ref{sec:approach}); empirically,
we show that the phenomenon is widespread across a range of
networks including preferential attachment networks. Our findings have implications for public 
policy and the distribution of vaccines. 
More surprisingly we observe that targeted vaccination can be strictly worse than
random vaccination for the same level of vaccine coverage and this phenomenon occurs both for one-sided
as well as two-sided risk behavior change (as shown in Figure \ref{fig:mh}). 
Given the prior work on targeting vaccine distributions 
this finding flies in the face of intuition that expects that vaccinating highly connected individuals would
confer greater benefits. 
}



\subsection{Incorporating temporal intervention strategies}
\label{sec:task2}
In practice, individuals decide about vaccinations depending on how
the disease is progressing; often these decisions are based on the
current prevalence of the disease, and the perceived effectiveness of
the vaccine. In this task, we propose to broaden the scope of the
earlier tasks and consider temporal strategies $a(v,t), b(v,t)$. Note
that even if a node $v$ is considering getting vaccinated, it need not
always be optimal to get vaccinated a the start of the epidemic -- for
instance, flu attack rates exhibit a temporal variation, and some
epidemics might die out on their own. In such an instance, a node $v$
might lower its cost by waiting for some time before getting
vaccinated, and its strategy vector could correspond to picking a
vector $(a(v,t), t)$.  Alternatively, the node could decide on the
vaccination dynamically depending on whether or not many of its
contacts have become infected or got vaccinated.  This motivates two
kinds of temporal strategies, each of which leads to a different
collection of research problems.

\smallskip
\BfPara{Task 3: Games with oblivious strategies} We plan to focus on
symmetric strategy vectors, with simplified behavioral modification
strategies, which are captured by the cost function (\ref{eqn:cost})
in Section \ref{sec:prelim}. In addition to understanding the
structure of NE, we propose to study whether specific public health
policies (viewed as coordinated equilibria, or in the context of
Stackelberg games) could mitigate the overall cost.

\smallskip
\noindent \emph{Technical approach and preliminary work.}  A strategy
vector ($\vec{a}, \vec{b}$) is chosen initially, and specifies a
fixed-time delay before vaccination.  Consider symmetric strategy
spaces in which each individual selects this delay according to a
common distribution.  In joint work with Galvani~\cite{reluga:mbs10},
we have analyzed such delay-based vaccination strategies using the
machinery of integro-differential equations.  The payoffs in this case
can be formulated as a Markov Decision Process (MDP).  We have
obtained closed-form expressions for mixed NE.  In basic scenarios,
there is a unique mixed NE for behavior with global invasion potential
that converges to the community's preferred policy for very
inexpensive and very expensive vaccines. But for more general
compartmental models, biological complications like limited vaccine
efficacy differences in immunity waning can lead to more complex
equilibrium structures.

Another temporal component of intervention strategies consists of the
decisions made based on past epidemic sizes.  In a game-theoretic
analysis~\cite{cornforth+rsbgm:flu}, we study the interplay between
contact patterns, influenza-related behavior, and disease dynamics,
find that individuals with many contacts vaccinate, whereas
individuals with few contacts do not. However, the threshold number of
contacts above which to vaccinate is highly dependent on the overall
network structure of the population and has the potential to oscillate
more wildly than has been observed empirically.  When the history,
i.e., the number of prior seasons that individuals recall when making
vaccination decisions is increased, behavior and thus disease
dynamics become less variable. For some networks, we also find that
higher flu transmission rates may, counter-intuitively, lead to lower
(vaccine-mediated) disease prevalence.

In \cite{reluga:bmb07}, we explore the relationship between
age-dependent virulence and behavior choices that affect transmission
through a population game based on a compartmental SIR model. We study
a model of transmission in a host population with two age classes, and
show that both high and low transmission rates can be Nash equilibria
of individual utility, depending on the contact rate's plasticity. One
Nash equilibrium minimizing transmission exists in cases where
virulence in juveniles is higher than virulence in adults but two Nash
equilibria can coexist under conditions of reduced virulence in
juveniles. When virulence in juveniles is less than that in adults,
one of these equilibria will exist at the maximum allowed transmission
rate, at which most individuals are infected as juveniles and avoid
infection as adults. The results show that there are situations where
the behaviors of individuals facilitate the transmission of a disease.

\iffalse
\item
The strategy vectors above are static, though they are temporal. In this task, we consider
a specific extension, in which we allow the behavioral modifications to be
more dynamic functions of time. Let $n(t)$ denote the number of infections at time
$t$. We allow $b(v,t)$ to be a simple function of $\frac{d n(t)}{dt}$ (e.g., 
$b(v,t)\propto -\frac{d n(t)}{dt}$). This part is the most exploratory task, and
would require developing techniques for analysis of this co-evolving process.
\fi

\smallskip
\BfPara{Task 4: Games with adaptive temporal strategies} We finally consider
adaptive temporal behavioral changes, in which the vaccination
strategies are determined in an on-line manner, (depending on the
states of the neighboring nodes).  We plan to build on the model of
Aspnes et al~\cite{aspnes+rs:worm}, in which the vaccination process
also spreads as a diffusion on a potentially different graph $H(V,E')$
(which could be an overlay or an information network). The vaccination
choices $a(v,t)$ depend on the current state of the neighbors of $v$
both in the contact graph $G$ as well as in the overlay graph $H$;
thus, this model combines the vaccination and behavioral change
strategies, allowing a more realistic user behavior.  The specific
questions we propose to study include:
\begin{enumerate}
\item
What are the structural properties of the overlay graph $H$ (relative
to the contact graph $G$), which ensure the existence of equilibria?

\item
The properties of the social optima, especially relative to the cost
of NE (e.g., price of anarchy), and strategies (from a public health
administrator's perspective) to influence the spread of vaccine
adoption are important questions. Since the vaccination process starts
off as another diffusion process, how and where to start it off are
important policy questions.
\end{enumerate}

\noindent{\emph{Technical approach and previous work.}}  One possible
approach to studying NE is to consider the time-expanded graphs
$(G(t), H(t))$, which capture the evolution of the graphs and the
dynamics, and consider payoffs averaged on this time horizon (in the
form of MDPs). An important issue would be to study the existence of
``low complexity'' strategies which do not take much of the history
into account. This might also require going beyond the standard notion
of NE to others, such as the subgame perfect NE (SPNE).

This component of the project incorporates all pieces of the strategy
space and is arguably the most complex to reason about.  We have no
prior published work in this area.  In preliminary analysis, however,
we have observed that (centralized) adaptive intervention techniques
can confer substantial benefits in terms of social good.  Intuitively,
this is not surprising since one can adapt the intervention policy --
both in terms of space (location) and time (when to act) -- to the
progression of the contagion.  This has also been confirmed by recent
simulations of~\cite{chowell+v:ada09} in the context of pandemic
influenza.  \junk{
\subsubsection{Preliminary Work}

In \cite{cornforth+rsbgm:flu}, we study 
the interplay between contact patterns, influenza-related behavior, and disease 
dynamics by incorporating game theory into network models. When individuals make 
decisions based on past epidemic sizes, we find that individuals with many contacts 
vaccinate, whereas individuals with few contacts do not. However, the threshold 
number of contacts above which to vaccinate is highly dependent on the overall network 
structure of the population and has the potential to oscillate more wildly than has 
been observed empirically.  When the history, i.e., the number of prior seasons 
that individuals recall when making vaccination decisions is increased, 
behavior and thus disease dynamics become less variable. For some
networks, we also find that higher flu transmission rates may, counter-intuitively, lead 
to lower (vaccine-mediated) disease prevalence. 

In \cite{reluga:bmb07}, we explore the relationship between
age-dependent virulence and behavior choices that affect transmission
through a population game based on a compartmental SIR model that
divides the population based on their susceptible, infected or
recovered (and immune) status. We study a model of transmission in a
host population with two age classes, and show that both high and low
transmission rates can be Nash equilibria of individual utility,
depending on the contact rate's plasticity. One Nash equilibrium
minimizing transmission exists in cases where virulence in juveniles
is higher than virulence in adults but two Nash equilibria can coexist
under conditions of reduced virulence in juveniles. When virulence in
juveniles is less than that in adults, one of these equilibria will
exist at the maximum allowed transmission rate, at which most
individuals are infected as juveniles and avoid infection as
adults. The results show that there are situations where the optimal
behaviors of individuals facilitate the transmission of a disease.
}

\junk{
\section{Our technical approach}
\label{sec:approach}

The questions we propose here are very challenging in general, and have a long
history of research in a number of disciplines, including computer science,
mathematics and physics. Our focus is on both on analytical as well as
simulation based results; there have been several advances in percolation theory as well as
agent based simulation tools in recent years (some of which the co-PIs have
participated in), which make it promising to exploit for this proposal. Some of
these are discussed here briefly.

\subsection{Percolation in finite graphs}
Percolation has been traditionally restricted to regular (e.g., cliques and grids)
or random graphs (e.g., Erdos-Renyi and Aeillo-Chung-Lu models) \cite{Ne03}. As discussed
earlier, we are interested in such models, as well as complex unstructured networks, for which
much less is is known. Our analytical approach builds on the following two powerful techniques
for analyzing percolation processes. Note that these techniques were originally developed for
specific settings, and require further refinement before they can be adopted for our problems.

\smallskip
\noindent
\emph{1. Multi-type branching processes for inhomogeneous random graphs}.
We discuss briefly the Soderberg \cite{soderberg+inhomo02} (which were
formalized subsequently by Bollobas and Riordan \cite{bollobas+inhomo}), which gives
a powerful tool for analyzing multi-type branching processes. 
Consider a random graph
model denoted by $\mathcal{G}(N,K,\textbf{r},\textbf{c})$, where
(i) $K$ is a positive integer\footnote{This is extended to a more general
setting by \cite{bollobas+inhomo}.}, (ii) $\textbf{r}=\{r_1,\ldots,r_K\}$ is a probability
vector, (iii) $\textbf{c}=(c_{ij})$ is a $K\times K$ matrix, (iv) each node 
$j=1,\ldots,N$, is assigned a type $i\in\{1,\ldots,K\}$ with probability $r_i$, and
(v) each pair of nodes $j, j'$ are connected by an edge with probability 
$p(j,j')=c_{ij}/N$. S\"{o}derberg \cite{soderberg+inhomo02} and Bollobas et al.
\cite{bollobas+inhomo} show the following powerful result:
\begin{theorem}
Let $\mathcal{G}(N,K,\textbf{r},\textbf{c})$ be the model discussed above. Then,
(i) if the eigenvalues of the matrix $\{c_{ij}r_j\}$ are all less than 1, 
it is sub-critical (i.e., has no giant component), and
(ii) if some eigenvalue is larger than 1, it is super-critical (i.e., has a giant
component) with asymptotically $r_i(1-f_i)N$ nodes of type $i$, where $f_i$
satisfies the coupled set of equations:
$f_i = exp\left(\sum_j c_{ij}r_j(f_j-1)\right)$.
\end{theorem}

As discussed earlier,
we used this in our work on the non-monotonic effect of risky behavior associated
with partly efficacious vaccine (Section \ref{sec:task1}) under a complete mixing
assumption; the unvaccinated, successfully and unsuccessfully vaccinated sets
correspond to the ``types'', and the above technique allows us to relate the giant
component size to the vaccination probability $p_v$. However, solving the above
coupled equations and bounding the fixed points $f_i$ becomes challenging for
more complex random graph models, such as the Aiello-Chung-Lu \cite{aiello+powerlawconn01};
we propose to extend and develop a more ``user-friendly'' version of this
technique, which is likely to be useful in other applications of percolation.

\smallskip
\noindent
\emph{2. Characterization in terms of the second order average degree
\cite{chung+hl:giant09}}.
The second technique we propose to build on is by Chung et al. \cite{chung+hl:giant09}
for percolation in arbitrary finite graphs. Define
$\tilde{d}=\sum_v d(v)^2/(\sum_v d(v))$, where $d(v)$ denotes the degree of node $v$
in graph $G=(V,E)$. Chung et al. prove that
\begin{theorem}
(i) If $p(e) < \frac{1}{\tilde{d}}$, then a.a.s., after percolation every component
$V'$ satisfies $\sum_{v\in V'} d(v)=O(\sqrt{\sum_w d(w)^2}g(n))$, where $g(n)$ is any
slowly growing function of $n$, and
(ii) if $p(e)>\frac{1}{\tilde{d}}$ and $G$ is ``$(\epsilon,M)$-admissible'', 
then a.a.s., after percolation there is a
giant component $V'$ such that $\sum_{v\in V'} d(v)=\Theta(\sum_{v\in V} d(v))$.
\end{theorem}

The notion of $(\epsilon,M)$-admissible is a technical condition, and many graphs,
such as constant degree graphs satisfy this. We propose to use this technique along with the
characterization of NE and social optima in our prior work \cite{kumar+rss:icdcs}
for some of the problems in Tasks 1 and 2 --
the social optimum corresponds to a clustering that minimizes the sum of
squares of cluster sizes, for the case $p(e)=1$ for all $e\in E$. From the
above technique, it follows that in the more general case of $p(e)<1$,
it suffices to focus on the contribution from clusters which have $\tilde{d}>1/p$;
it is still challenging to extend this idea to get rigorous bounds on the
quality of approximation.
}

\subsection{Agent based models and realistic synthetic networks}
\label{sec:simulations}
As outlined in the research tasks of Sections~\ref{sec:task1}
and~\ref{sec:task2}, a major component of this project is the study of
diffusion processes on unstructured complex networks.  A natural way
to validate the proposed methods and develop new approaches is by
analyzing real-world and synthetic data sets and running simulation
tools.  Two challenges arise in this regard.
\begin{NoIndentEnumerate}
\item
Data for social contact networks, especially those representing
physical co-location contacts (necessary for the spread of epidemics)
are hard to obtain. There are a number of models for such networks
(see, e.g., \cite{Ne03}), such as scale free models based on the
preferential attachment process of Barabasi et
al. \cite{barabasi:science99} or the rank-1 model of Aiello et
al. \cite{aiello:stoc00}; see the survey by Newman \cite{Ne03} for a
detailed discussion on the properties of a number of these models. The
specific models are important because their properties have a
significant impact on the dynamics of diffusion processes, as has been
observed by a number of researchers, e.g., \cite{Ne03, EG+04}.

\item
Tools for the simulation of diffusion processes on large scale
networks are difficult to develop owing to the unstructured nature of
the network and the lack of symmetry; this renders traditional
approaches for load balancing infeasible for simulating networks of
realistic size.
\end{NoIndentEnumerate}
We have experience in both these aspects.  The Virginia Tech team has
developed models of synthetic social contact networks using first
principles based approaches which integrate a number of different data
sets, such as census and land use (see \cite{barrett:wsc09,EG+04} for
details on the methodology for constructing such networks). In
addition to random graph models such as scale-free networks, we will
use these real-world social contact networks as part of this proposal.
Co-PI Vullikanti also has experience in agent based methods, which we
will build upon in this proposal.  In \cite{bisset:ics09}, we have
developed Epifast, an efficient agent based simulation tool for the
spread of epidemics on large social contact networks using a new
result on extension of percolation to directed weighted graphs; this
result reduces epidemic simulations to shortest paths on random
weighted graphs, and we have obtained several orders of magnitude
speed-up in epidemic simulations on large contact graphs. Epifast is
also capable of handling a number of different interventions,
including vaccinations, anti-virals and social distancing measures
(e.g., closing schools). We have extended this to another tool called
EpiNet \cite{epinet-karthik-simutools09}, simulating the spread of
malware in wireless Bluetooth networks; we find that significantly
simplified worm models that do not require any Bluetooth states are
capable of modeling the worm dynamics very effectively, by suitable
calibration. These simulation tools will be used in the computational
part of the proposal.

\junk{There are very few models of large social networks. We will use the
synthetic social contact network models developed by the Virginia Tech
team \cite{ EG+04}, in order to extend our insights from
random graph and complete mixing models to realistic networks, thereby
addressing more relevant policy level questions.
}
\section{Research Team, Expertise and Coordination Plan}
\label{sec:team}

The team consists of PI Ravi Sundaram (Northeastern University) and
Co-PIs Rajmohan Rajaraman (Northeastern University), Tim Reluga (Penn
State University), and Anil Vullikanti (Virginia Tech). In addition,
Zhengzheng Pan, a postdoctoral associate at Virginia Tech, will be
partially supported by this project, together with graduate students in
the three institutions. The team collectively has experience in all
the aspects of this proposal, as discussed below.
\begin{NoIndentEnumerate}
\item
Game theory and Dynamical Systems:
Sundaram, Rajaraman and Vullikanti have studied problems in algorithmic game theory, e.g.,
\cite{kintali+prst:fractional, laoutaris+prst:game, rajaraman:dialm10, kumar:icalp02, eidenbenz06}, especially those arising from communication networking
applications, such as sensor networks and the Internet, and 
problems related to computational aspects of discrete dynamical systems,
such as stability and reachability \cite{kumar:rp09, tripathi:ciac10}. Reluga
has studied game theoretical formulations arising in epidemiology, especially
those involving interventions such as vaccination and social distancing
\cite{galvani+rc:influenza07, cornforth+rsbgm:flu, reluga:plos10, 
reluga:bmb07}; some of this work also examines current public health policies
from such a perspective \cite{reluga:plos10}.
\item
Mathematical and computational epidemiology:
Reluga is a mathematical epidemiologist and in addition to game theoretical
formulations, has studied other aspects of epidemiology in the SIR and SIS
models \cite{reluga+medlock, reluga:jtb08, reluga:bmb07}. 
Vullikanti has focused on computational aspects of epidemiology, such as developing faster simulations
and strategies for detection and control in the SIR model, especially the
public health aspects \cite{halloran:pnas08, EG+04}; he has also
studied other models for contagion, e.g., those based on thresholds \cite{kuhlman:pkdd10}.
\item
Complex networks: Network models form an important basis of this project, and
simple random graph models do not adequately capture many important properties
of real systems. Vullikanti has worked on developing first principles approaches
for synthetic social contact networks, and using them for the study of disease
dynamics and cellular network traffic modeling
\cite{EG+04, kmps:soda04, beckman:dyspan10,
barrett:wsc09}. An important step in this work is to develop efficient methods
for computing graph properties, which we have studied in
\cite{zhaozhao:icpp10, kmps:soda04}.
\item
Distributed algorithms: 
This area involves the development of decentralized algorithms, with agents using local
information and coordination to achieve a global task. The research team collectively has
a lot of experience in developing efficient distributed algorithms for a
number of problems 
\cite{laoutaris+prst:game, chen+rs:capacity, arias:spaa03, rajaraman:spaa01,
khan:infocom09, choi:jsac09, khan:tcs07}

\item
Agent based simulation: Diffusion processes on complex unstructured networks
cannot be easily studied analytically and Vullikanti has worked on developing large scale
agent based simulation tools for epidemics and malware
\cite{epinet-karthik-simutools09, bisset:ics09}. These will be used in this
project.
\end{NoIndentEnumerate}

\smallskip
\noindent
\emph{Coordination Plan}: Though the co-PIs are spatially separated,
they will ensure regular coordination and collaboration by means of
conference calls and visits to each others campuses. Sundaram,
Rajaraman and Vullikanti have collaborated together for over two
years, including co-advising of students and campus visits; this will
be further strengthened by visits of the co-PIs and their students.
Vullikanti has also visited Reluga at Penn State.  Furthermore,
Zhengzheng Pan, the postdoctoral associate will interact closely with
students from all the teams, and greatly facilitate the coordination
of this project.

\input{edu}

\input{prior}

\newpage

\setcounter{page}{1}
\bibliographystyle{plain}
\bibliography{ices,refs}
 
\end{document}
